#include "trie.hpp"

#include <utility>
#include <algorithm>
#include <iostream>


bool trie::erase(const std::string& str) {
     bool found=false;
   
    if(this->m_size>0 ){
        if(str.size()==0){
            for(int i=1;i<=this->m_size;i++){
                if(this->m_root->children[i]->children[0]->payload=='0'){
                    found= true;
                    delete this->m_root->children[i]->children[0];
                    this->m_root->children[i]->children[0]=nullptr;
                    
                    //delete this->m_root->children[i]->parent;
                    this->m_root->children[i]->parent=nullptr;
                    
                    delete this->m_root->children[i];
                    this->m_root->children[i]=nullptr;
                   
                    for(int y=i;y<this->m_size;y++){
                        this->m_root->children[y]=this->m_root->children[y+1];
    
                    }
                    this->m_size--;
                    break;
                }
            
            }
        }
        else{
            for (int x=1; x<=this->m_size;x++){
                 int counter=0,y=0;
                                     

                while(this->m_root->children[x]->children[y]->is_terminal!=true){
                    counter++;
                    y++;
                }
                 counter++;
                 if(counter==str.size()){
                    for(int u=0;u<counter;u++){
                        if(str.at(u)==this->m_root->children[x]->children[u]->payload){
                            found=true;
                        }else{
                            found=false;
                            break;
                        }
                    
                    }
                    if(found==true){
                        for(int m=0;m<str.size();m++){
                            delete this->m_root->children[x]->children[m];
                            //delete this->m_root->children[x]->parent;
                            this->m_root->children[x]->children[m]=nullptr;
                            this->m_root->children[x]->parent=nullptr;
                            
                        
                        }
                        delete this->m_root->children[x];
                        this->m_root->children[x]=nullptr;
                       
                         for(int m=x;m<this->m_size;m++){
                            this->m_root->children[m]=this->m_root->children[m+1];
    
                         }
                        this->m_size--;
                        return true;
                        
                    }
                 
                 
                 }
            
            
            }
        
        }
    }
    return found;

}

bool trie::insert(const std::string& str) {
   
     
   
     if(! contains(str)){
        if(str.length()==0){
             m_size++;
             m_root->children[ m_size]=new trie_node;
             m_root->children[ m_size]->payload='1'; 
             m_root->children[ m_size]->is_terminal=true; 
             m_root->children[m_size]->parent=m_root;
             
             if(m_size>1){m_root->children[ m_size-1]->is_terminal=false;} 

             m_root->children[ m_size]->children[0]= new trie_node;
             m_root->children[ m_size]->children[0]->payload='0';
             m_root->children[ m_size]->children[0]->is_terminal=true;
             m_root->children[ m_size]->children[0]->parent= m_root->children[ m_size];

        }else{
             m_size++;
             m_root->children[ m_size]=new trie_node;
             m_root->children[ m_size]->payload='1';
             m_root->children[ m_size]->is_terminal=true; 
                          m_root->children[m_size]->parent=m_root;

             if(m_size>1){m_root->children[ m_size-1]->is_terminal=false;} 

            for(int i=0;i<str.length();i++){
                 m_root->children[ m_size]->children[i]= new trie_node;
                 m_root->children[ m_size]->children[i]->payload=str.at(i);
                 m_root->children[ m_size]->children[i]->parent=   m_root->children[ m_size];

            if(i==str.length()-1){
                   m_root->children[this->m_size]->children[i]->is_terminal=true;
               }
        }}
        return true;
    }
    
    
    return false;
}

bool trie::contains(const std::string& str) const {
   
     bool found=false;
   
    if(this->m_size>0 ){
        if(str.size()==0){
            for(int i=1;i<=this->m_size;i++){
                if(this->m_root->children[i]->children[0]->payload=='0'){
                    found= true;
                    break;
                }
            
            }
        }
        else{
            for (int x=1; x<=this->m_size;x++){
                 int counter=0,y=0;
                                     

                while(this->m_root->children[x]->children[y]->is_terminal!=true){
                    counter++;
                    y++;
                }
                 counter++;
                 if(counter==str.size()){
                    for(int u=0;u<counter;u++){
                        if(str.at(u)==this->m_root->children[x]->children[u]->payload){
                            found=true;
                        }else{
                            found=false;
                            break;
                        }
                    
                    }
                    if(found==true){
                        return true;
                        
                    }
                 
                 
                 }
            
            
            }
        
        }
    }
    return found;
}


trie::trie() {
    
    delete m_root;
   m_root=new trie_node;
    m_size= 0;
   m_root->is_terminal=false;
   m_root->payload='0';

}

trie::trie(const std::vector<std::string>& strings) {
    this->m_root=new trie_node;
    
   this->m_root->is_terminal=false;
   this->m_root->payload='0';

 for (int i=0; i<strings.size();i++) {
        insert(strings.at(i));
    }

}

trie::~trie() {
 for(int i=0;i<=m_size;i++){
     
         int x=0;
         if(m_root->children[i]!=nullptr){
                  while(m_root->children[i]->children[x]->is_terminal!=true){
                      
                      m_root->children[i]->children[x]->parent=nullptr;
                      delete m_root->children[i]->children[x];
                      m_root->children[i]->children[x]=nullptr;
                      
                      
                      x++;  
                  }
                  
                  m_root->children[i]->children[x]->parent=nullptr;
                  delete m_root->children[i]->children[x];
                  m_root->children[i]->children[x]=nullptr;
                    }
                  delete m_root->children[i];
                  m_root->children[i]=nullptr;
    
    }
   delete m_root;
   m_root=nullptr;
   m_size=0;
   
}

size_t trie::size() const {
    return this->m_size;
}

bool trie::empty() const {
    return this->m_size==0;
}


std::vector<std::string> trie::search_by_prefix(const std::string& str) const {
    word_cursor iterator=this->get_word_cursor();
    std::vector<std::string> returnVector;
    returnVector.reserve(m_size);

    std::string readString;
    int y=0;
    bool matches=true;
    
    while (iterator.has_word()) {
        
        readString=iterator.read_word();
        if(readString.length()>=str.length()){
            for(int i=0;i<str.length();i++){
                if(readString.at(i)!=str.at(i)){
                    matches=false;
                    break;
                }
            
            }
            if(matches){
                returnVector.push_back(readString);
                y++;
            }
        
        
        }
        matches=true;
        iterator.move_to_next_word();
    }

 return returnVector;   
}

std::vector<std::string> trie::get_prefixes(const std::string& str) const {
      word_cursor iterator=this->get_word_cursor();
    std::vector<std::string> returnVector;
    returnVector.reserve(m_size);
    std::string readString;
    int y=0;
    
    bool matches=true;
    
    while (iterator.has_word()) {
       
        readString=iterator.read_word();
        if(readString.length()<=str.length()){
            for(int i=0;i<readString.length();i++){
                if(readString.at(i)!=str.at(i)){
                    matches=false;
                    break;
                }
            
            }
            if(matches){
                returnVector.push_back(readString);
                y++;
            }
        
        
        }
        matches=true;
        iterator.move_to_next_word();
    }

 return returnVector;   
}

word_cursor trie::get_word_cursor() const {
    return word_cursor(this->m_root->children[1]);
}

bool word_cursor::has_word() const {
    return !(m_ptr==nullptr);
}

std::string word_cursor::read_word() const {
    std::string returnString="";
    int i=0;
    if (m_ptr->children[0]->is_terminal&&m_ptr->children[0]->payload!='0') {
        returnString+=m_ptr->children[0]->payload;
        return returnString;

    }

    do{
         
        if((m_ptr->children[i]->payload=='0'&&i==0)){break;}
        returnString+=m_ptr->children[i]->payload;
       
       i++;
    }
    while(!m_ptr->children[i]->is_terminal);
    if(i!=0 ){returnString+=m_ptr->children[i]->payload;}
    return returnString;
}

void word_cursor::move_to_next_word() {
    bool match=true;
    int i=0,x=0;
    if(m_ptr==nullptr){return;}
    if(m_ptr->is_terminal){
        m_ptr=nullptr;
        return;
    }
    do{
        i++;
        match=true;
        while(!m_ptr->children[x]->is_terminal)
        {
           
            if(m_ptr->parent->children[i]->children[x]->is_terminal){
                match=false;
                 
                break;
            }
            if((m_ptr->parent->children[i]->children[x])!=m_ptr->children[x]){
                match=false;
                
                break;
            }
            
            x++;
        
        }
        
        if(!m_ptr->parent->children[i]->children[x]->is_terminal){
                match=false;
                
                
            }
            if((m_ptr->parent->children[i]->children[x])!=m_ptr->children[x]){
                match=false;
                
            }
        
        if(match){
            m_ptr=m_ptr->parent->children[i+1];
            
            break;
        }
      
                   
    }
    while (!m_ptr->parent->children[i]->is_terminal) ;
  
    

}

word_cursor::word_cursor(const trie_node* ptr) {
    m_ptr=ptr;
}
